The present invention relates to arbitration schemes for use in computer systems. More particularly, the invention provides for an arbitration scheme having a local arbiter for each device in the system which requires use of the channel, the local arbiter being programmable to provide either a linear priority arbitration technique or a fairness priority arbitration technique.
Presently, there are various arbitration schemes in existence which determine the order in which multiple devices in a computer system may gain access to the channel. The majority of schemes generally fall into one of two categories, namely a centralized arbitration scheme or a distributed arbitration scheme. In both schemes each device has a priority value associated with it which is compared to the priority values of other devices contending for use of the channel, with the device having the highest value winning access to the channel. However, in the centralized scheme the winning device is determined at a central device, such as a CPU, while in a distributed scheme each device makes its own determination if it is the winning device (i.e. highest priority device requesting access to the channel).
The most common arbitration schemes, whether centralized or distributed, utilize a linear priority arbitration technique in which the highest priority device generally maintains control of the bus as long as it may require, and thus may prevent lower priority level devices from gaining access to the bus for inordinate periods of time. This might ultimately result in overrun conditions in the lower priority devices.
Another solution is commonly referred to as a fairness priority arbitration technique in which each device is given an opportunity to gain access to the bus, after the highest priority device has relinguished control of the bus and before the highest priority device may regain control of the bus. One such technique prevents the device presently in control of the bus from contending for the next bus cycle, and generally works well for single transfer devices. However, this will allow first and second devices to trade off but together both devices may lock out a third device. Another type of fairness priority arbitration technique is shown in the Intel Manual for the 8289 device and is illustrated on page 2-196 of that document, the same technique again being illustrated in the Intel Manual for the 82289 device on page 3-167. In both instances, a centralized arbitration scheme is implemented in which a rotating priority resolving technique is utilized. A special circuit rotates priority between requesting devices, thus allowing each device an equal chance to use the multi-master system bus over a given period of time. Therefore, all the devices contending for the bus are required to participate in the rotating priority technique.
It is readily apparent from the aforesaid discussion that both the centralized arbitration scheme and the distributed arbitration scheme were originally designed so that all the devices working in the scheme operate either utilizing the linear priority arbitration technique or the fairness priority arbitration technique. However, with the addition of burst transfer devices intermingled with single transfer devices it became desirable to have a hybrid priority arbitration technique in which some devices may operate under the linear priority arbitration technique and other devices operate under the fairness priority arbitration technique.
One such hybrid technique, described in the article entitled "Arbitration and Control Acquisition in the Proposed IEEE 896 Futurebus" by D. M. Taub, found in the August 1984 issue of IEEE Micro, describes an arbitration scheme in which potential masters (PM's) are divided into two classes. The first class contains priority modules, whose need for the bus may be particularly urgent, for instance because of having to cope with realtime operations. The second class contains fairness modules, whose need for the bus is less urgent. Priority modules issue a request for the bus whenever they need it, and compete in the arbitration process the next time it occurs. On the other hand, once a fairness module has had control of the bus, it desists from issuing further bus requests until there are no requests left to service. However, each PM is preselected to be either a fairness module or a priority module and thus is not dynamically programmable to accommodate the varying needs of the user and/or different computer applications.
The present invention in the preferred embodiment contemplates an improved hybrid system by providing a dynamically programmable circuit in each local arbiter which allows either the linear priority arbitration technique or the fairness priority arbitration technique to be initiated depending upon the particular needs of the user and/or the application software being utilized.
Accordingly, it is an object of the present invention to provide a computer system having a dynamically programmable arbitration circuit for initiating either a linear priority arbitration technique or a fairness priority arbitration technique for each device requiring access to the system bus.
It is another object of the present invention to provide a computer system having a distributed priority arbitration scheme in which each device requiring access to the system bus employs a local arbiter associated therewith, the local arbiter having a circuit which is programmable to allow the local arbiter to initiate either a linear priority arbitration technique or a fairness priority arbitration technique.
It is yet another object of the present invention to provide a computer system having a distributed dynamically programmable linear/fairness priority arbitration scheme which accommodates a mixture of single transfer devices and burst transfer devices.